package backMind

import "fmt"

// 8皇后问题
// 每个皇后所在列
var result [8]int

func EightQueen() {
	CalQueens(0)
}

// CalQueens row 表示第i个皇后，也就是当前第i行
func CalQueens(row int) {
	// 结束条件
	// 8个皇后都放好了
	if row == 8 {
		printQueens(result)
		return
	}
	// 对于每个皇后来讲都有8种放置方法（每一行的8个列位置）
	// 从第0列开始考察，直到最后一个；每个皇后占一行，所以不用考虑行问题
	for column := 0; column < 8; column++ {
		// 有些放置位置不满足要求
		if isOk(row, column) {
			// 第row行的皇后放到了column列
			result[row] = column
			// 继续放置下一个皇后，也就是考察下一行的皇后放置问题
			CalQueens(row + 1)
		}
		// 只有当前的皇后能安置，才能继续后面的皇后，否则说明这条路走不通
	}
}

// 打印二维矩阵
func printQueens(result [8]int) {
	for row := 0; row < 8; row++ {
		for column := 0; column < 8; column++ {
			if result[row] == column {
				fmt.Print("Q ")
			} else {
				fmt.Print("* ")
			}
		}
		fmt.Println()
	}
	fmt.Println()
}

// 判断row行column列放置是否符合要求
func isOk(row, column int) bool {
	var left = column - 1
	var right = column + 1
	// 依次检查当前皇后的位置是否对已安置皇后的位置构成冲突
	for i := row - 1; i >= 0; i-- {
		// 因为每一行都只放一个皇后，所以行方向不需要检查
		// 检查列方向是否有皇后
		if result[i] == column {
			return false
		}
		// 检查左对角线，第i行left列是否有皇后
		if left >= 0 {
			if result[i] == left {
				return false
			}
		}
		// 检查右对角线，第i行right是否有皇后
		if right < len(result) {
			if result[i] == right {
				return false
			}
		}
		// 左对角线方向上left在往左移动
		left--
		// 右对角线方向上right在往右移动
		right++
	}
	return true
}
